home *** CD-ROM | disk | FTP | other *** search
/ Computer Shopper 242 / Issue 242 - April 2008 - DPCS0408DVD.ISO / Software Money Savers / VirtualDub / Source / VirtualDub-1.7.7-src.7z / src / Kasumi / source / region.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2007-08-17  |  31.0 KB  |  1,292 lines
  1. //    VirtualDub - Video processing and capture application
  2. //    Graphics support library
  3. //    Copyright (C) 1998-2007 Avery Lee
  4. //
  5. //    This program is free software; you can redistribute it and/or modify
  6. //    it under the terms of the GNU General Public License as published by
  7. //    the Free Software Foundation; either version 2 of the License, or
  8. //    (at your option) any later version.
  9. //
  10. //    This program is distributed in the hope that it will be useful,
  11. //    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. //    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. //    GNU General Public License for more details.
  14. //
  15. //    You should have received a copy of the GNU General Public License
  16. //    along with this program; if not, write to the Free Software
  17. //    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19. #include <vd2/Kasumi/pixmap.h>
  20. #include <vd2/Kasumi/pixmaputils.h>
  21. #include <vd2/Kasumi/region.h>
  22. #include <vd2/system/math.h>
  23. #include <vd2/system/vdstl.h>
  24.  
  25. void VDPixmapRegion::swap(VDPixmapRegion& x) {
  26.     mSpans.swap(x.mSpans);
  27.     std::swap(mBounds, x.mBounds);
  28. }
  29.  
  30. VDPixmapPathRasterizer::VDPixmapPathRasterizer()
  31.     : mpEdgeBlocks(NULL)
  32.     , mEdgeBlockIdx(kEdgeBlockMax)
  33.     , mpScanBuffer(NULL)
  34. {
  35.     ClearScanBuffer();
  36. }
  37.  
  38. VDPixmapPathRasterizer::~VDPixmapPathRasterizer() {
  39.     Clear();
  40. }
  41.  
  42. void VDPixmapPathRasterizer::Clear() {
  43.     ClearEdgeList();
  44.     ClearScanBuffer();
  45. }
  46.  
  47. void VDPixmapPathRasterizer::QuadraticBezier(const vdint2 *pts) {
  48.     int x0 = pts[0].x;
  49.     int x1 = pts[1].x;
  50.     int x2 = pts[2].x;
  51.     int y0 = pts[0].y;
  52.     int y1 = pts[1].y;
  53.     int y2 = pts[2].y;
  54.  
  55.     // P = (1-t)^2*P0 + 2t(1-t)*P1 + t^2*P2
  56.     // P = (1-2t+t^2)P0 + 2(t-t^2)P1 + t^2*P2
  57.     // P = (P0-2P1+P2)t^2 + 2(P1-P0)t + P0
  58.  
  59.     int cx2 =    x0-2*x1+x2;
  60.     int cx1 = -2*x0+2*x1;
  61.     int cx0 =    x0;
  62.  
  63.     int cy2 =    y0-2*y1+y2;
  64.     int cy1 = -2*y0+2*y1;
  65.     int cy0 =    y0;
  66.  
  67.     // This equation is from Graphics Gems I.
  68.     //
  69.     // The idea is that since we're approximating a cubic curve with lines,
  70.     // any error we incur is due to the curvature of the line, which we can
  71.     // estimate by calculating the maximum acceleration of the curve.  For
  72.     // a cubic, the acceleration (second derivative) is a line, meaning that
  73.     // the absolute maximum acceleration must occur at either the beginning
  74.     // (|c2|) or the end (|c2+c3|).  Our bounds here are a little more
  75.     // conservative than that, but that's okay.
  76.     //
  77.     // If the acceleration of the parametric formula is zero (c2 = c3 = 0),
  78.     // that component of the curve is linear and does not incur any error.
  79.     // If a=0 for both X and Y, the curve is a line segment and we can
  80.     // use a step size of 1.
  81.  
  82.     int maxaccel1 = abs(cy2);
  83.     int maxaccel2 = abs(cx2);
  84.  
  85.     int maxaccel = maxaccel1 > maxaccel2 ? maxaccel1 : maxaccel2;
  86.     int h = 1;
  87.  
  88.     while(maxaccel > 8 && h < 1024) {
  89.         maxaccel >>= 2;
  90.         h += h;
  91.     }
  92.  
  93.     int lastx = x0;
  94.     int lasty = y0;
  95.  
  96.     // compute forward differences
  97.     sint64 h1 = (sint64)(0x40000000 / h) << 2;
  98.     sint64 h2 = h1/h;
  99.  
  100.     sint64 ax0 = (sint64)cx0 << 32;
  101.     sint64 ax1 =   h1*(sint64)cx1 +   h2*(sint64)cx2;
  102.     sint64 ax2 = 2*h2*(sint64)cx2;
  103.  
  104.     sint64 ay0 = (sint64)cy0 << 32;
  105.     sint64 ay1 =   h1*(sint64)cy1 +   h2*(sint64)cy2;
  106.     sint64 ay2 = 2*h2*(sint64)cy2;
  107.  
  108.     // round, not truncate
  109.     ax0 += 0x80000000;
  110.     ay0 += 0x80000000;
  111.  
  112.     do {
  113.         ax0 += ax1;
  114.         ax1 += ax2;
  115.         ay0 += ay1;
  116.         ay1 += ay2;
  117.  
  118.         int xi = (int)((uint64)ax0 >> 32);
  119.         int yi = (int)((uint64)ay0 >> 32);
  120.  
  121.         FastLine(lastx, lasty, xi, yi);
  122.         lastx = xi;
  123.         lasty = yi;
  124.     } while(--h);
  125. }
  126.  
  127. void VDPixmapPathRasterizer::CubicBezier(const vdint2 *pts) {
  128.     int x0 = pts[0].x;
  129.     int x1 = pts[1].x;
  130.     int x2 = pts[2].x;
  131.     int x3 = pts[3].x;
  132.     int y0 = pts[0].y;
  133.     int y1 = pts[1].y;
  134.     int y2 = pts[2].y;
  135.     int y3 = pts[3].y;
  136.  
  137.     int cx3 = -  x0+3*x1-3*x2+x3;
  138.     int cx2 =  3*x0-6*x1+3*x2;
  139.     int cx1 = -3*x0+3*x1;
  140.     int cx0 =    x0;
  141.  
  142.     int cy3 = -  y0+3*y1-3*y2+y3;
  143.     int cy2 =  3*y0-6*y1+3*y2;
  144.     int cy1 = -3*y0+3*y1;
  145.     int cy0 =    y0;
  146.  
  147.     // This equation is from Graphics Gems I.
  148.     //
  149.     // The idea is that since we're approximating a cubic curve with lines,
  150.     // any error we incur is due to the curvature of the line, which we can
  151.     // estimate by calculating the maximum acceleration of the curve.  For
  152.     // a cubic, the acceleration (second derivative) is a line, meaning that
  153.     // the absolute maximum acceleration must occur at either the beginning
  154.     // (|c2|) or the end (|c2+c3|).  Our bounds here are a little more
  155.     // conservative than that, but that's okay.
  156.     //
  157.     // If the acceleration of the parametric formula is zero (c2 = c3 = 0),
  158.     // that component of the curve is linear and does not incur any error.
  159.     // If a=0 for both X and Y, the curve is a line segment and we can
  160.     // use a step size of 1.
  161.  
  162.     int maxaccel1 = abs(2*cy2) + abs(6*cy3);
  163.     int maxaccel2 = abs(2*cx2) + abs(6*cx3);
  164.  
  165.     int maxaccel = maxaccel1 > maxaccel2 ? maxaccel1 : maxaccel2;
  166.     int h = 1;
  167.  
  168.     while(maxaccel > 8 && h < 1024) {
  169.         maxaccel >>= 2;
  170.         h += h;
  171.     }
  172.  
  173.     int lastx = x0;
  174.     int lasty = y0;
  175.  
  176.     // compute forward differences
  177.     sint64 h1 = (sint64)(0x40000000 / h) << 2;
  178.     sint64 h2 = h1/h;
  179.     sint64 h3 = h2/h;
  180.  
  181.     sint64 ax0 = (sint64)cx0 << 32;
  182.     sint64 ax1 =   h1*(sint64)cx1 +   h2*(sint64)cx2 + h3*(sint64)cx3;
  183.     sint64 ax2 = 2*h2*(sint64)cx2 + 6*h3*(sint64)cx3;
  184.     sint64 ax3 = 6*h3*(sint64)cx3;
  185.  
  186.     sint64 ay0 = (sint64)cy0 << 32;
  187.     sint64 ay1 =   h1*(sint64)cy1 +   h2*(sint64)cy2 + h3*(sint64)cy3;
  188.     sint64 ay2 = 2*h2*(sint64)cy2 + 6*h3*(sint64)cy3;
  189.     sint64 ay3 = 6*h3*(sint64)cy3;
  190.  
  191.     // round, not truncate
  192.     ax0 += 0x80000000;
  193.     ay0 += 0x80000000;
  194.  
  195.     do {
  196.         ax0 += ax1;
  197.         ax1 += ax2;
  198.         ax2 += ax3;
  199.         ay0 += ay1;
  200.         ay1 += ay2;
  201.         ay2 += ay3;
  202.  
  203.         int xi = (int)((uint64)ax0 >> 32);
  204.         int yi = (int)((uint64)ay0 >> 32);
  205.  
  206.         FastLine(lastx, lasty, xi, yi);
  207.         lastx = xi;
  208.         lasty = yi;
  209.     } while(--h);
  210. }
  211.  
  212. void VDPixmapPathRasterizer::Line(const vdint2& pt1, const vdint2& pt2) {
  213.     FastLine(pt1.x, pt1.y, pt2.x, pt2.y);
  214. }
  215.  
  216. void VDPixmapPathRasterizer::FastLine(int x0, int y0, int x1, int y1) {
  217.     int flag = 1;
  218.  
  219.     if (y1 == y0)
  220.         return;
  221.  
  222.     if (y1 < y0) {
  223.         int t;
  224.  
  225.         t=x0; x0=x1; x1=t;
  226.         t=y0; y0=y1; y1=t;
  227.         flag = 0;
  228.     }
  229.  
  230.     int dy = y1-y0;
  231.     int xacc = x0<<13;
  232.  
  233.     // prestep y0 down
  234.     int iy0 = (y0+3) >> 3;
  235.     int iy1 = (y1+3) >> 3;
  236.  
  237.     if (iy0 < iy1) {
  238.         int invslope = (x1-x0)*65536/dy;
  239.  
  240.         int prestep = (4-y0) & 7;
  241.         xacc += (invslope * prestep)>>3;
  242.  
  243.         if (iy0 < mScanYMin || iy1 > mScanYMax) {
  244.             ReallocateScanBuffer(iy0, iy1);
  245.             VDASSERT(iy0 >= mScanYMin && iy1 <= mScanYMax);
  246.         }
  247.  
  248.         while(iy0 < iy1) {
  249.             int ix = (xacc+32767)>>16;
  250.  
  251.             if (mEdgeBlockIdx >= kEdgeBlockMax) {
  252.                 mpEdgeBlocks = new EdgeBlock(mpEdgeBlocks);
  253.                 mEdgeBlockIdx = 0;
  254.             }
  255.  
  256.             Edge& e = mpEdgeBlocks->edges[mEdgeBlockIdx];
  257.             Scan& s = mpScanBufferBiased[iy0];
  258.             VDASSERT(iy0 >= mScanYMin && iy0 < mScanYMax);
  259.             ++mEdgeBlockIdx;
  260.  
  261.             e.posandflag = ix*2+flag;
  262.             e.next = s.chain;
  263.             s.chain = &e;
  264.             ++s.count;
  265.  
  266.             ++iy0;
  267.             xacc += invslope;
  268.         }
  269.     }
  270. }
  271.  
  272. void VDPixmapPathRasterizer::ScanConvert(VDPixmapRegion& region) {
  273.     // Convert the edges to spans.  We couldn't do this before because some of
  274.     // the regions may have winding numbers >+1 and it would have been a pain
  275.     // to try to adjust the spans on the fly.  We use one heap to detangle
  276.     // a scanline's worth of edges from the singly-linked lists, and another
  277.     // to collect the actual scans.
  278.     vdfastvector<int> heap;
  279.  
  280.     region.mSpans.clear();
  281.     int xmin = INT_MAX;
  282.     int xmax = INT_MIN;
  283.     int ymin = INT_MAX;
  284.     int ymax = INT_MIN;
  285.  
  286.     for(int y=mScanYMin; y<mScanYMax; ++y) {
  287.         uint32 flipcount = mpScanBufferBiased[y].count;
  288.  
  289.         if (!flipcount)
  290.             continue;
  291.  
  292.         // Keep the edge heap from doing lots of stupid little reallocates.
  293.         if (heap.capacity() < flipcount)
  294.             heap.resize((flipcount + 63)&~63);
  295.  
  296.         // Detangle scanline into edge heap.
  297.         int *heap0 = heap.data();
  298.         int *heap1 = heap0;
  299.         for(const Edge *ptr = mpScanBufferBiased[y].chain; ptr; ptr = ptr->next)
  300.             *heap1++ = ptr->posandflag;
  301.  
  302.         VDASSERT(heap1 - heap0 == flipcount);
  303.  
  304.         // Sort edge heap.  Note that we conveniently made the opening edges
  305.         // one more than closing edges at the same spot, so we won't have any
  306.         // problems with abutting spans.
  307.  
  308.         std::sort(heap0, heap1);
  309.  
  310. #if 0
  311.         while(heap0 != heap1) {
  312.             int x = *heap0++ >> 1;
  313.             region.mSpans.push_back((y<<16) + x + 0x80008000);
  314.             region.mSpans.push_back((y<<16) + x + 0x80008001);
  315.         }
  316.         continue;
  317. #endif
  318.  
  319.         // Trim any odd edges off, since we can never close on one.
  320.         if (flipcount & 1)
  321.             --heap1;
  322.  
  323.         // Process edges and add spans.  Since we only check for a non-zero
  324.         // winding number, it doesn't matter which way the outlines go. Also, since
  325.         // the parity always flips after each edge regardless of direction, we can
  326.         // process the edges in pairs.
  327.  
  328.         size_t spanstart = region.mSpans.size();
  329.  
  330.         int x_left;
  331.         int count = 0;
  332.         while(heap0 != heap1) {
  333.             int x = *heap0++;
  334.  
  335.             if (!count)
  336.                 x_left = (x>>1);
  337.  
  338.             count += (x&1);
  339.  
  340.             x = *heap0++;
  341.  
  342.             count += (x&1);
  343.  
  344.             if (!--count) {
  345.                 int x_right = (x>>1);
  346.  
  347.                 if (x_right > x_left) {
  348.                     region.mSpans.push_back((y<<16) + x_left  + 0x80008000);
  349.                     region.mSpans.push_back((y<<16) + x_right + 0x80008000);
  350.  
  351.                 }
  352.             }
  353.         }
  354.  
  355.         size_t spanend = region.mSpans.size();
  356.  
  357.         if (spanend > spanstart) {
  358.             if (ymin > y)
  359.                 ymin = y;
  360.  
  361.             if (ymax < y)
  362.                 ymax = y;
  363.  
  364.             int x1 = (region.mSpans[spanstart] & 0xffff) - 0x8000;
  365.             int x2 = (region.mSpans[spanend-1] & 0xffff) - 0x8000;
  366.  
  367.             if (xmin > x1)
  368.                 xmin = x1;
  369.  
  370.             if (xmax < x2)
  371.                 xmax = x2;
  372.         }
  373.     }
  374.  
  375.     if (xmax > xmin) {
  376.         region.mBounds.set(xmin, ymin, xmax, ymax);
  377.     } else {
  378.         region.mBounds.set(0, 0, 0, 0);
  379.     }
  380.  
  381.     // Dump the edge and scan buffers, since we no longer need them.
  382.     ClearEdgeList();
  383.     ClearScanBuffer();
  384. }
  385.  
  386. void VDPixmapPathRasterizer::ClearEdgeList() {
  387.     while(EdgeBlock *block = mpEdgeBlocks) {
  388.         mpEdgeBlocks = block->next;
  389.  
  390.         delete block;
  391.     }
  392.     mEdgeBlockIdx = kEdgeBlockMax;
  393. }
  394.  
  395. void VDPixmapPathRasterizer::ClearScanBuffer() {
  396.     delete[] mpScanBuffer;
  397.     mpScanBuffer = mpScanBufferBiased = NULL;
  398.     mScanYMin = mScanYMax = 0;
  399. }
  400.  
  401. void VDPixmapPathRasterizer::ReallocateScanBuffer(int ymin, int ymax) {
  402.     // check if there actually is a scan buffer to avoid unintentionally pinning at zero
  403.     if (mpScanBuffer) {
  404.         // enforce a minimal growth factor of 1.25 to get amortized linear behavior
  405.         int nicedelta = ((mScanYMax - mScanYMin) >> 2);
  406.  
  407.         if (ymin < mScanYMin) {
  408.             int yminnice = mScanYMin - nicedelta;
  409.             if (ymin > yminnice)
  410.                 ymin = yminnice;
  411.  
  412.             ymin &= ~31;
  413.         } else
  414.             ymin = mScanYMin;
  415.  
  416.         if (ymax > mScanYMax) {
  417.             int ymaxnice = mScanYMax + nicedelta;
  418.             if (ymax < ymaxnice)
  419.                 ymax = ymaxnice;
  420.  
  421.             ymax = (ymax + 31) & ~31;
  422.         } else
  423.             ymax = mScanYMax;
  424.  
  425.         VDASSERT(ymin <= mScanYMin && ymax >= mScanYMax);
  426.     }
  427.  
  428.     // reallocate scan buffer
  429.     Scan *pNewBuffer = new Scan[ymax - ymin];
  430.     Scan *pNewBufferBiased = pNewBuffer - ymin;
  431.  
  432.     if (mpScanBuffer) {
  433.         memcpy(pNewBufferBiased + mScanYMin, mpScanBufferBiased + mScanYMin, (mScanYMax - mScanYMin) * sizeof(Scan));
  434.         delete[] mpScanBuffer;
  435.  
  436.         // zero new areas of scan buffer
  437.         vdfor(int y=ymin; y<mScanYMin; ++y) {
  438.             pNewBufferBiased[y].chain = NULL;
  439.             pNewBufferBiased[y].count = 0;
  440.         }
  441.         vdfor(int y=mScanYMax; y<ymax; ++y) {
  442.             pNewBufferBiased[y].chain = NULL;
  443.             pNewBufferBiased[y].count = 0;
  444.         }
  445.     } else {
  446.         vdfor(int y=ymin; y<ymax; ++y) {
  447.             pNewBufferBiased[y].chain = NULL;
  448.             pNewBufferBiased[y].count = 0;
  449.         }
  450.     }
  451.  
  452.     mpScanBuffer = pNewBuffer;
  453.     mpScanBufferBiased = pNewBufferBiased;
  454.     mScanYMin = ymin;
  455.     mScanYMax = ymax;
  456. }
  457.  
  458. bool VDPixmapFillRegion(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
  459.     if (dst.format != nsVDPixmap::kPixFormat_XRGB8888)
  460.         return false;
  461.  
  462.     // fast out
  463.     if (region.mSpans.empty())
  464.         return true;
  465.  
  466.     // check if vertical clipping is required
  467.     const size_t n = region.mSpans.size();
  468.     uint32 start = 0;
  469.     uint32 end = n;
  470.  
  471.     uint32 spanmin = (-x) + ((-y) << 16) + 0x80008000;
  472.  
  473.     if (region.mSpans.front() < spanmin) {
  474.         uint32 lo = 0, hi = n;
  475.  
  476.         // compute top clip
  477.         while(lo < hi) {
  478.             int mid = ((lo + hi) >> 1) & ~1;
  479.  
  480.             if (region.mSpans[mid + 1] < spanmin)
  481.                 lo = mid + 2;
  482.             else
  483.                 hi = mid;
  484.         }
  485.  
  486.         start = lo;
  487.  
  488.         // check for total top clip
  489.         if (start >= n)
  490.             return true;
  491.     }
  492.  
  493.     uint32 spanlimit = (dst.w - x) + ((dst.h - y - 1) << 16) + 0x80008000;
  494.  
  495.     if (region.mSpans.back() > spanlimit) {
  496.         // compute bottom clip
  497.         int lo = start;
  498.         int hi = n;
  499.  
  500.         while(lo < hi) {
  501.             int mid = ((lo + hi) >> 1) & ~1;
  502.  
  503.             if (region.mSpans[mid] >= spanlimit)
  504.                 hi = mid;
  505.             else
  506.                 lo = mid+2;
  507.         }
  508.  
  509.         end = lo;
  510.  
  511.         // check for total bottom clip
  512.         if (start >= end)
  513.             return true;
  514.     }
  515.  
  516.     // fill region
  517.     const uint32 *pSpan = ®ion.mSpans[start];
  518.     const uint32 *pEnd  = ®ion.mSpans[0] + end;
  519.     int lasty = -1;
  520.     uint32 *dstp;
  521.  
  522.     for(; pSpan != pEnd; pSpan += 2) {
  523.         uint32 span0 = pSpan[0];
  524.         uint32 span1 = pSpan[1];
  525.  
  526.         uint32 py = (span0 >> 16) - 0x8000 + y;
  527.         uint32 px = (span0 & 0xffff) - 0x8000 + x;
  528.         uint32 w = span1-span0;
  529.  
  530.         VDASSERT(py < (uint32)dst.h);
  531.         VDASSERT(px < (uint32)dst.w);
  532.         VDASSERT(dst.w - (int)px >= (int)w);
  533.  
  534.         if (lasty != py)
  535.             dstp = (uint32 *)vdptroffset(dst.data, dst.pitch * py);
  536.  
  537.         uint32 *p = dstp + px;
  538.         do {
  539.             *p++ = color;
  540.         } while(--w);
  541.     }
  542.  
  543.     return true;
  544. }
  545.  
  546. namespace {
  547.     void RenderABuffer32(const VDPixmap& dst, int y, const uint8 *alpha, uint32 w, uint32 color) {
  548.         if (!w)
  549.             return;
  550.  
  551.         // update dest pointer
  552.         uint32 *dstp = (uint32 *)vdptroffset(dst.data, dst.pitch * y);
  553.  
  554.         const uint32 color_rb = color & 0x00FF00FF;
  555.         const uint32 color_g  = color & 0x0000FF00;
  556.         do {
  557.             const uint32 px = *dstp;
  558.             const uint32 px_rb = px & 0x00FF00FF;
  559.             const uint32 px_g  = px & 0x0000FF00;
  560.             const sint32 a     = *alpha++;
  561.  
  562.             const uint32 result_rb = (((px_rb << 6) + ((sint32)(color_rb - px_rb)*a + 0x00200020)) & 0x3FC03FC0);
  563.             const uint32 result_g  = (((px_g  << 6) + ((sint32)(color_g  - px_g )*a + 0x00002000)) & 0x003FC000);
  564.  
  565.             *dstp++ = (result_rb + result_g) >> 6;
  566.         } while(--w);
  567.     }
  568.  
  569.     void RenderABuffer8(const VDPixmap& dst, int y, const uint8 *alpha, uint32 w, uint32 color) {
  570.         if (!w)
  571.             return;
  572.  
  573.         // update dest pointer
  574.         uint8 *dstp = (uint8 *)vdptroffset(dst.data, dst.pitch * y);
  575.  
  576.         do {
  577.             const uint8 px = *dstp;
  578.             const sint8 a = *alpha++;
  579.  
  580.             *dstp++ = px + (((sint32)(color - px) * a + 32) >> 6);
  581.         } while(--w);
  582.     }
  583.  
  584.     void RenderABuffer8_128(const VDPixmap& dst, int y, const uint8 *alpha, uint32 w, uint32 color) {
  585.         if (!w)
  586.             return;
  587.  
  588.         // update dest pointer
  589.         uint8 *dstp = (uint8 *)vdptroffset(dst.data, dst.pitch * y);
  590.  
  591.         do {
  592.             const uint8 px = *dstp;
  593.             const sint16 a = *alpha++;
  594.  
  595.             *dstp++ = px + (((sint32)(color - px) * a + 64) >> 7);
  596.         } while(--w);
  597.     }
  598.  
  599.     void RenderABuffer8_256(const VDPixmap& dst, int y, const uint16 *alpha, uint32 w, uint32 color) {
  600.         if (!w)
  601.             return;
  602.  
  603.         // update dest pointer
  604.         uint8 *dstp = (uint8 *)vdptroffset(dst.data, dst.pitch * y);
  605.  
  606.         do {
  607.             const uint8 px = *dstp;
  608.             const sint32 a = *alpha++;
  609.  
  610.             *dstp++ = px + (((sint32)(color - px) * a + 128) >> 8);
  611.         } while(--w);
  612.     }
  613.  
  614.     void RenderABuffer8_1024(const VDPixmap& dst, int y, const uint16 *alpha, uint32 w, uint32 color) {
  615.         if (!w)
  616.             return;
  617.  
  618.         // update dest pointer
  619.         uint8 *dstp = (uint8 *)vdptroffset(dst.data, dst.pitch * y);
  620.  
  621.         do {
  622.             const uint8 px = *dstp;
  623.             const sint32 a = *alpha++;
  624.  
  625.             *dstp++ = px + (((sint32)(color - px) * a + 512) >> 10);
  626.         } while(--w);
  627.     }
  628. }
  629.  
  630. bool VDPixmapFillRegionAntialiased_32x_32x(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
  631.     if (dst.format != nsVDPixmap::kPixFormat_Y8)
  632.         return false;
  633.  
  634.     // fast out
  635.     if (region.mSpans.empty())
  636.         return true;
  637.  
  638.     // check if vertical clipping is required
  639.     const size_t n = region.mSpans.size();
  640.     uint32 start = 0;
  641.     uint32 end = n;
  642.  
  643.     uint32 spanmin = -x + (-y << 16) + 0x80008000;
  644.  
  645.     if (region.mSpans.front() < spanmin) {
  646.         // find first span : x2 > spanmin
  647.         start = std::upper_bound(region.mSpans.begin(), region.mSpans.end(), spanmin) - region.mSpans.begin();
  648.         start &= ~1;
  649.  
  650.         // check for total top clip
  651.         if (start >= n)
  652.             return true;
  653.     }
  654.  
  655.     uint32 spanlimit = (dst.w*32 - x) + (((dst.h*32 - y) - 1) << 16) + 0x80008000;
  656.  
  657.     if (region.mSpans.back() > spanlimit) {
  658.         // find last span : x1 < spanlimit
  659.         end = std::lower_bound(region.mSpans.begin(), region.mSpans.end(), spanlimit) - region.mSpans.begin();
  660.  
  661.         end = (end + 1) & ~1;
  662.  
  663.         // check for total bottom clip
  664.         if (start >= end)
  665.             return true;
  666.     }
  667.  
  668.     // allocate A-buffer
  669.     vdfastvector<uint16> abuffer(dst.w, 0);
  670.  
  671.     // fill region
  672.     const uint32 *pSpan = ®ion.mSpans[start];
  673.     const uint32 *pEnd  = ®ion.mSpans[0] + end;
  674.     int lasty = -1;
  675.  
  676.     sint32 dstw32 = dst.w * 32;
  677.     sint32 dsth32 = dst.h * 32;
  678.  
  679.     for(; pSpan != pEnd; pSpan += 2) {
  680.         uint32 span0 = pSpan[0];
  681.         uint32 span1 = pSpan[1];
  682.  
  683.         sint32 py = (span0 >> 16) - 0x8000 + y;
  684.  
  685.         if ((uint32)py >= (uint32)dsth32)
  686.             continue;
  687.  
  688.         sint32 px1 = (span0 & 0xffff) - 0x8000 + x;
  689.         sint32 px2 = (span1 & 0xffff) - 0x8000 + x;
  690.         sint32 w = span1-span0;
  691.  
  692.         if (lasty != py) {
  693.             if (((lasty ^ py) & 0xFFFFFFE0)) {
  694.                 if (lasty >= 0) {
  695.                     // flush scanline
  696.  
  697.                     RenderABuffer8_1024(dst, lasty >> 5, abuffer.data(), dst.w, color);
  698.                 }
  699.  
  700.                 memset(abuffer.data(), 0, abuffer.size() * sizeof(abuffer[0]));
  701.             }
  702.             lasty = py;
  703.         }
  704.  
  705.         if (px1 < 0)
  706.             px1 = 0;
  707.         if (px2 > dstw32)
  708.             px2 = dstw32;
  709.  
  710.         if (px1 >= px2)
  711.             continue;
  712.  
  713.         uint32 ix1 = px1 >> 5;
  714.         uint32 ix2 = px2 >> 5;
  715.         uint16 *p1 = abuffer.data() + ix1;
  716.         uint16 *p2 = abuffer.data() + ix2;
  717.  
  718.         if (p1 == p2) {
  719.             p1[0] += (px2 - px1);
  720.         } else {
  721.             if (px1 & 31) {
  722.                 p1[0] += 32 - (px1 & 31);
  723.                 ++p1;
  724.             }
  725.  
  726.             while(p1 != p2) {
  727.                 p1[0] += 32;
  728.                 ++p1;
  729.             }
  730.  
  731.             if (px2 & 31)
  732.                 p1[0] += px2 & 32;
  733.         }
  734.     }
  735.  
  736.     if (lasty >= 0)
  737.         RenderABuffer8_1024(dst, lasty >> 5, abuffer.data(), dst.w, color);
  738.  
  739.     return true;
  740. }
  741.  
  742. bool VDPixmapFillRegionAntialiased_16x_16x(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
  743.     if (dst.format != nsVDPixmap::kPixFormat_Y8)
  744.         return false;
  745.  
  746.     // fast out
  747.     if (region.mSpans.empty())
  748.         return true;
  749.  
  750.     // check if vertical clipping is required
  751.     const size_t n = region.mSpans.size();
  752.     uint32 start = 0;
  753.     uint32 end = n;
  754.  
  755.     uint32 spanmin = -x + (-y << 16) + 0x80008000;
  756.  
  757.     if (region.mSpans.front() < spanmin) {
  758.         // find first span : x2 > spanmin
  759.         start = std::upper_bound(region.mSpans.begin(), region.mSpans.end(), spanmin) - region.mSpans.begin();
  760.         start &= ~1;
  761.  
  762.         // check for total top clip
  763.         if (start >= n)
  764.             return true;
  765.     }
  766.  
  767.     uint32 spanlimit = (dst.w*16 - x) + (((dst.h*16 - y) - 1) << 16) + 0x80008000;
  768.  
  769.     if (region.mSpans.back() > spanlimit) {
  770.         // find last span : x1 < spanlimit
  771.         end = std::lower_bound(region.mSpans.begin(), region.mSpans.end(), spanlimit) - region.mSpans.begin();
  772.  
  773.         end = (end + 1) & ~1;
  774.  
  775.         // check for total bottom clip
  776.         if (start >= end)
  777.             return true;
  778.     }
  779.  
  780.     // allocate A-buffer
  781.     vdfastvector<uint16> abuffer(dst.w, 0);
  782.  
  783.     // fill region
  784.     const uint32 *pSpan = ®ion.mSpans[start];
  785.     const uint32 *pEnd  = ®ion.mSpans[0] + end;
  786.     int lasty = -1;
  787.  
  788.     sint32 dstw16 = dst.w * 16;
  789.     sint32 dsth16 = dst.h * 16;
  790.  
  791.     for(; pSpan != pEnd; pSpan += 2) {
  792.         uint32 span0 = pSpan[0];
  793.         uint32 span1 = pSpan[1];
  794.  
  795.         sint32 py = (span0 >> 16) - 0x8000 + y;
  796.  
  797.         if ((uint32)py >= (uint32)dsth16)
  798.             continue;
  799.  
  800.         sint32 px1 = (span0 & 0xffff) - 0x8000 + x;
  801.         sint32 px2 = (span1 & 0xffff) - 0x8000 + x;
  802.         sint32 w = span1-span0;
  803.  
  804.         if (lasty != py) {
  805.             if (((lasty ^ py) & 0xFFFFFFF0)) {
  806.                 if (lasty >= 0) {
  807.                     // flush scanline
  808.  
  809.                     RenderABuffer8_256(dst, lasty >> 4, abuffer.data(), dst.w, color);
  810.                 }
  811.  
  812.                 memset(abuffer.data(), 0, abuffer.size() * sizeof(abuffer[0]));
  813.             }
  814.             lasty = py;
  815.         }
  816.  
  817.         if (px1 < 0)
  818.             px1 = 0;
  819.         if (px2 > dstw16)
  820.             px2 = dstw16;
  821.  
  822.         if (px1 >= px2)
  823.             continue;
  824.  
  825.         uint32 ix1 = px1 >> 4;
  826.         uint32 ix2 = px2 >> 4;
  827.         uint16 *p1 = abuffer.data() + ix1;
  828.         uint16 *p2 = abuffer.data() + ix2;
  829.  
  830.         if (p1 == p2) {
  831.             p1[0] += (px2 - px1);
  832.         } else {
  833.             if (px1 & 15) {
  834.                 p1[0] += 16 - (px1 & 15);
  835.                 ++p1;
  836.             }
  837.  
  838.             while(p1 != p2) {
  839.                 p1[0] += 16;
  840.                 ++p1;
  841.             }
  842.  
  843.             if (px2 & 15)
  844.                 p1[0] += px2 & 15;
  845.         }
  846.     }
  847.  
  848.     if (lasty >= 0)
  849.         RenderABuffer8_256(dst, lasty >> 4, abuffer.data(), dst.w, color);
  850.  
  851.     return true;
  852. }
  853.  
  854. bool VDPixmapFillRegionAntialiased_16x_8x(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
  855.     if (dst.format != nsVDPixmap::kPixFormat_XRGB8888 && dst.format != nsVDPixmap::kPixFormat_Y8)
  856.         return false;
  857.  
  858.     // fast out
  859.     if (region.mSpans.empty())
  860.         return true;
  861.  
  862.     // check if vertical clipping is required
  863.     const size_t n = region.mSpans.size();
  864.     uint32 start = 0;
  865.     uint32 end = n;
  866.  
  867.     uint32 spanmin = -x + (-y << 16) + 0x80008000;
  868.  
  869.     if (region.mSpans.front() < spanmin) {
  870.         // find first span : x2 > spanmin
  871.         start = std::upper_bound(region.mSpans.begin(), region.mSpans.end(), spanmin) - region.mSpans.begin();
  872.         start &= ~1;
  873.  
  874.         // check for total top clip
  875.         if (start >= n)
  876.             return true;
  877.     }
  878.  
  879.     uint32 spanlimit = (dst.w*16 - x) + (((dst.h*8 - y) - 1) << 16) + 0x80008000;
  880.  
  881.     if (region.mSpans.back() > spanlimit) {
  882.         // find last span : x1 < spanlimit
  883.         end = std::lower_bound(region.mSpans.begin(), region.mSpans.end(), spanlimit) - region.mSpans.begin();
  884.  
  885.         end = (end + 1) & ~1;
  886.  
  887.         // check for total bottom clip
  888.         if (start >= end)
  889.             return true;
  890.     }
  891.  
  892.     // allocate A-buffer
  893.     vdfastvector<uint8> abuffer(dst.w, 0);
  894.  
  895.     // fill region
  896.     const uint32 *pSpan = ®ion.mSpans[start];
  897.     const uint32 *pEnd  = ®ion.mSpans[0] + end;
  898.     int lasty = -1;
  899.  
  900.     sint32 dstw16 = dst.w * 16;
  901.     sint32 dsth8 = dst.h * 8;
  902.  
  903.     for(; pSpan != pEnd; pSpan += 2) {
  904.         uint32 span0 = pSpan[0];
  905.         uint32 span1 = pSpan[1];
  906.  
  907.         sint32 py = (span0 >> 16) - 0x8000 + y;
  908.  
  909.         if ((uint32)py >= (uint32)dsth8)
  910.             continue;
  911.  
  912.         sint32 px1 = (span0 & 0xffff) - 0x8000 + x;
  913.         sint32 px2 = (span1 & 0xffff) - 0x8000 + x;
  914.         sint32 w = span1-span0;
  915.  
  916.         if (lasty != py) {
  917.             if (((lasty ^ py) & 0xFFFFFFF8)) {
  918.                 if (lasty >= 0) {
  919.                     // flush scanline
  920.  
  921.                     RenderABuffer8_128(dst, lasty >> 3, abuffer.data(), dst.w, color);
  922.                 }
  923.  
  924.                 memset(abuffer.data(), 0, abuffer.size());
  925.             }
  926.             lasty = py;
  927.         }
  928.  
  929.         if (px1 < 0)
  930.             px1 = 0;
  931.         if (px2 > dstw16)
  932.             px2 = dstw16;
  933.  
  934.         if (px1 >= px2)
  935.             continue;
  936.  
  937.         uint32 ix1 = px1 >> 4;
  938.         uint32 ix2 = px2 >> 4;
  939.         uint8 *p1 = abuffer.data() + ix1;
  940.         uint8 *p2 = abuffer.data() + ix2;
  941.  
  942.         if (p1 == p2) {
  943.             p1[0] += (px2 - px1);
  944.         } else {
  945.             if (px1 & 15) {
  946.                 p1[0] += 16 - (px1 & 15);
  947.                 ++p1;
  948.             }
  949.  
  950.             while(p1 != p2) {
  951.                 p1[0] += 16;
  952.                 ++p1;
  953.             }
  954.  
  955.             if (px2 & 15)
  956.                 p1[0] += px2 & 15;
  957.         }
  958.     }
  959.  
  960.     if (lasty >= 0)
  961.         RenderABuffer8_128(dst, lasty >> 3, abuffer.data(), dst.w, color);
  962.  
  963.     return true;
  964. }
  965.  
  966. bool VDPixmapFillRegionAntialiased8x(const VDPixmap& dst, const VDPixmapRegion& region, int x, int y, uint32 color) {
  967.     if (dst.format == nsVDPixmap::kPixFormat_YUV444_Planar ||
  968.         dst.format == nsVDPixmap::kPixFormat_YUV422_Planar ||
  969.         dst.format == nsVDPixmap::kPixFormat_YUV420_Planar ||
  970.         dst.format == nsVDPixmap::kPixFormat_YUV410_Planar) {
  971.         VDPixmap pxY;
  972.         VDPixmap pxCb;
  973.         VDPixmap pxCr;
  974.  
  975.         pxY.format = nsVDPixmap::kPixFormat_Y8;
  976.         pxY.data = dst.data;
  977.         pxY.pitch = dst.pitch;
  978.         pxY.w = dst.w;
  979.         pxY.h = dst.h;
  980.  
  981.         pxCb.format = nsVDPixmap::kPixFormat_Y8;
  982.         pxCb.data = dst.data2;
  983.         pxCb.pitch = dst.pitch2;
  984.         pxCb.h = dst.h;
  985.  
  986.         pxCr.format = nsVDPixmap::kPixFormat_Y8;
  987.         pxCr.data = dst.data3;
  988.         pxCr.pitch = dst.pitch3;
  989.         pxCr.h = dst.h;
  990.  
  991.         uint32 colorY = (color >> 8) & 0xff;
  992.         uint32 colorCb = (color >> 0) & 0xff;
  993.         uint32 colorCr = (color >> 16) & 0xff;
  994.  
  995.         VDPixmapFillRegionAntialiased8x(pxY, region, x, y, colorY);
  996.  
  997.         switch(dst.format) {
  998.         case nsVDPixmap::kPixFormat_YUV410_Planar:
  999.             pxCr.w = pxCb.w = dst.w >> 2;
  1000.             pxCr.h = pxCb.h = dst.h >> 2;
  1001.             x >>= 2;
  1002.             y >>= 2;
  1003.             VDPixmapFillRegionAntialiased_32x_32x(pxCb, region, x, y, colorCb);
  1004.             VDPixmapFillRegionAntialiased_32x_32x(pxCr, region, x, y, colorCr);
  1005.             return true;
  1006.         case nsVDPixmap::kPixFormat_YUV420_Planar:
  1007.             pxCr.w = pxCb.w = dst.w >> 1;
  1008.             pxCr.h = pxCb.h = dst.h >> 1;
  1009.             x >>= 1;
  1010.             y >>= 1;
  1011.             x += 2;
  1012.             VDPixmapFillRegionAntialiased_16x_16x(pxCb, region, x, y, colorCb);
  1013.             VDPixmapFillRegionAntialiased_16x_16x(pxCr, region, x, y, colorCr);
  1014.             return true;
  1015.         case nsVDPixmap::kPixFormat_YUV422_Planar:
  1016.             pxCr.w = pxCb.w = dst.w >> 1;
  1017.             x >>= 1;
  1018.             x += 2;
  1019.             VDPixmapFillRegionAntialiased_16x_8x(pxCb, region, x, y, colorCb);
  1020.             VDPixmapFillRegionAntialiased_16x_8x(pxCr, region, x, y, colorCr);
  1021.             return true;
  1022.         case nsVDPixmap::kPixFormat_YUV444_Planar:
  1023.             VDPixmapFillRegionAntialiased8x(pxCb, region, x, y, colorCb);
  1024.             VDPixmapFillRegionAntialiased8x(pxCr, region, x, y, colorCr);
  1025.             return true;
  1026.         }
  1027.     }
  1028.  
  1029.     if (dst.format != nsVDPixmap::kPixFormat_XRGB8888 && dst.format != nsVDPixmap::kPixFormat_Y8)
  1030.         return false;
  1031.  
  1032.     // fast out
  1033.     if (region.mSpans.empty())
  1034.         return true;
  1035.  
  1036.     // check if vertical clipping is required
  1037.     const size_t n = region.mSpans.size();
  1038.     uint32 start = 0;
  1039.     uint32 end = n;
  1040.  
  1041.     uint32 spanmin = -x + (-y << 16) + 0x80008000;
  1042.  
  1043.     if (region.mSpans.front() < spanmin) {
  1044.         // find first span : x2 > spanmin
  1045.         start = std::upper_bound(region.mSpans.begin(), region.mSpans.end(), spanmin) - region.mSpans.begin();
  1046.         start &= ~1;
  1047.  
  1048.         // check for total top clip
  1049.         if (start >= n)
  1050.             return true;
  1051.     }
  1052.  
  1053.     uint32 spanlimit = (dst.w*8 - x) + (((dst.h*8 - y) - 1) << 16) + 0x80008000;
  1054.  
  1055.     if (region.mSpans.back() > spanlimit) {
  1056.         // find last span : x1 < spanlimit
  1057.         end = std::lower_bound(region.mSpans.begin(), region.mSpans.end(), spanlimit) - region.mSpans.begin();
  1058.  
  1059.         end = (end + 1) & ~1;
  1060.  
  1061.         // check for total bottom clip
  1062.         if (start >= end)
  1063.             return true;
  1064.     }
  1065.  
  1066.     // allocate A-buffer
  1067.     vdfastvector<uint8> abuffer(dst.w, 0);
  1068.  
  1069.     // fill region
  1070.     const uint32 *pSpan = ®ion.mSpans[start];
  1071.     const uint32 *pEnd  = ®ion.mSpans[0] + end;
  1072.     int lasty = -1;
  1073.  
  1074.     sint32 dstw8 = dst.w * 8;
  1075.     sint32 dsth8 = dst.h * 8;
  1076.  
  1077.     for(; pSpan != pEnd; pSpan += 2) {
  1078.         uint32 span0 = pSpan[0];
  1079.         uint32 span1 = pSpan[1];
  1080.  
  1081.         sint32 py = (span0 >> 16) - 0x8000 + y;
  1082.  
  1083.         if ((uint32)py >= (uint32)dsth8)
  1084.             continue;
  1085.  
  1086.         sint32 px1 = (span0 & 0xffff) - 0x8000 + x;
  1087.         sint32 px2 = (span1 & 0xffff) - 0x8000 + x;
  1088.         sint32 w = span1-span0;
  1089.  
  1090.         if (lasty != py) {
  1091.             if (((lasty ^ py) & 0xFFFFFFF8)) {
  1092.                 if (lasty >= 0) {
  1093.                     // flush scanline
  1094.  
  1095.                     if (dst.format == nsVDPixmap::kPixFormat_XRGB8888)
  1096.                         RenderABuffer32(dst, lasty >> 3, abuffer.data(), dst.w, color);
  1097.                     else
  1098.                         RenderABuffer8(dst, lasty >> 3, abuffer.data(), dst.w, color);
  1099.                 }
  1100.  
  1101.                 memset(abuffer.data(), 0, abuffer.size());
  1102.             }
  1103.             lasty = py;
  1104.         }
  1105.  
  1106.         if (px1 < 0)
  1107.             px1 = 0;
  1108.         if (px2 > dstw8)
  1109.             px2 = dstw8;
  1110.  
  1111.         if (px1 >= px2)
  1112.             continue;
  1113.  
  1114.         uint32 ix1 = px1 >> 3;
  1115.         uint32 ix2 = px2 >> 3;
  1116.         uint8 *p1 = abuffer.data() + ix1;
  1117.         uint8 *p2 = abuffer.data() + ix2;
  1118.  
  1119.         if (p1 == p2) {
  1120.             p1[0] += (px2 - px1);
  1121.         } else {
  1122.             if (px1 & 7) {
  1123.                 p1[0] += 8 - (px1 & 7);
  1124.                 ++p1;
  1125.             }
  1126.  
  1127.             while(p1 != p2) {
  1128.                 p1[0] += 8;
  1129.                 ++p1;
  1130.             }
  1131.  
  1132.             if (px2 & 7)
  1133.                 p1[0] += px2 & 7;
  1134.         }
  1135.     }
  1136.  
  1137.     if (lasty >= 0) {
  1138.         if (dst.format == nsVDPixmap::kPixFormat_XRGB8888)
  1139.             RenderABuffer32(dst, lasty >> 3, abuffer.data(), dst.w, color);
  1140.         else
  1141.             RenderABuffer8(dst, lasty >> 3, abuffer.data(), dst.w, color);
  1142.     }
  1143.  
  1144.     return true;
  1145. }
  1146.  
  1147. void VDPixmapCreateRoundRegion(VDPixmapRegion& dst, float r) {
  1148.     int ir = VDCeilToInt(r);
  1149.     float r2 = r*r;
  1150.  
  1151.     dst.mSpans.clear();
  1152.     dst.mBounds.set(-ir, 0, ir+1, 0);
  1153.  
  1154.     for(int y = -ir; y <= ir; ++y) {
  1155.         int dx = VDCeilToInt(sqrtf(r2 - y*y));
  1156.  
  1157.         if (dx > 0) {
  1158.             dst.mSpans.push_back(0x80008000 + (y << 16) - dx);
  1159.             dst.mSpans.push_back(0x80008001 + (y << 16) + dx);
  1160.             if (dst.mBounds.top > y)
  1161.                 dst.mBounds.top = y;
  1162.             if (dst.mBounds.bottom < y)
  1163.                 dst.mBounds.bottom = y;
  1164.         }
  1165.     }
  1166. }
  1167.  
  1168. void VDPixmapConvolveRegion(VDPixmapRegion& dst, const VDPixmapRegion& r1, const VDPixmapRegion& r2, int dx1, int dx2, int dy) {
  1169.     dst.mSpans.clear();
  1170.     dst.mSpans.resize(r1.mSpans.size()+r2.mSpans.size());
  1171.  
  1172.     const uint32 *itA    = r1.mSpans.data();
  1173.     const uint32 *itAE    = itA + r1.mSpans.size();
  1174.     const uint32 *itB    = r2.mSpans.data();
  1175.     const uint32 *itBE    = itB + r2.mSpans.size();
  1176.     uint32 *dstp0 = dst.mSpans.data();
  1177.     uint32 *dstp = dst.mSpans.data();
  1178.  
  1179.     uint32 offset1 = (dy<<16) + dx1;
  1180.     uint32 offset2 = (dy<<16) + dx2;
  1181.  
  1182.     while(itA != itAE && itB != itBE) {
  1183.         uint32 x1;
  1184.         uint32 x2;
  1185.  
  1186.         if (itB[0] + offset1 < itA[0]) {
  1187.             // B span is earlier.  Use it.
  1188.             x1 = itB[0] + offset1;
  1189.             x2 = itB[1] + offset2;
  1190.             itB += 2;
  1191.  
  1192.             // B spans *can* overlap, due to the widening.
  1193.             while(itB != itBE && itB[0]+offset1 <= x2) {
  1194.                 uint32 bx2 = itB[1] + offset2;
  1195.                 if (x2 < bx2)
  1196.                     x2 = bx2;
  1197.  
  1198.                 itB += 2;
  1199.             }
  1200.  
  1201.             goto a_start;
  1202.         } else {
  1203.             // A span is earlier.  Use it.
  1204.             x1 = itA[0];
  1205.             x2 = itA[1];
  1206.             itA += 2;
  1207.  
  1208.             // A spans don't overlap, so begin merge loop with B first.
  1209.         }
  1210.  
  1211.         for(;;) {
  1212.             // If we run out of B spans or the B span doesn't overlap,
  1213.             // then the next A span can't either (because A spans don't
  1214.             // overlap) and we exit.
  1215.  
  1216.             if (itB == itBE || itB[0]+offset1 > x2)
  1217.                 break;
  1218.  
  1219.             do {
  1220.                 uint32 bx2 = itB[1] + offset2;
  1221.                 if (x2 < bx2)
  1222.                     x2 = bx2;
  1223.  
  1224.                 itB += 2;
  1225.             } while(itB != itBE && itB[0]+offset1 <= x2);
  1226.  
  1227.             // If we run out of A spans or the A span doesn't overlap,
  1228.             // then the next B span can't either, because we would have
  1229.             // consumed all overlapping B spans in the above loop.
  1230. a_start:
  1231.             if (itA == itAE || itA[0] > x2)
  1232.                 break;
  1233.  
  1234.             do {
  1235.                 uint32 ax2 = itA[1];
  1236.                 if (x2 < ax2)
  1237.                     x2 = ax2;
  1238.  
  1239.                 itA += 2;
  1240.             } while(itA != itAE && itA[0] <= x2);
  1241.         }
  1242.  
  1243.         // Flush span.
  1244.         dstp[0] = x1;
  1245.         dstp[1] = x2;
  1246.         dstp += 2;
  1247.     }
  1248.  
  1249.     // Copy over leftover spans.
  1250.     memcpy(dstp, itA, sizeof(uint32)*(itAE - itA));
  1251.     dstp += itAE - itA;
  1252.  
  1253.     while(itB != itBE) {
  1254.         // B span is earlier.  Use it.
  1255.         uint32 x1 = itB[0] + offset1;
  1256.         uint32 x2 = itB[1] + offset2;
  1257.         itB += 2;
  1258.  
  1259.         // B spans *can* overlap, due to the widening.
  1260.         while(itB != itBE && itB[0]+offset1 <= x2) {
  1261.             uint32 bx2 = itB[1] + offset2;
  1262.             if (x2 < bx2)
  1263.                 x2 = bx2;
  1264.  
  1265.             itB += 2;
  1266.         }
  1267.  
  1268.         dstp[0] = x1;
  1269.         dstp[1] = x2;
  1270.         dstp += 2;
  1271.     }
  1272.  
  1273.     dst.mSpans.resize(dstp - dst.mSpans.data());
  1274. }
  1275.  
  1276. void VDPixmapConvolveRegion(VDPixmapRegion& dst, const VDPixmapRegion& r1, const VDPixmapRegion& r2) {
  1277.     VDPixmapRegion temp;
  1278.  
  1279.     const uint32 *src1 = r2.mSpans.data();
  1280.     const uint32 *src2 = src1 + r2.mSpans.size();
  1281.  
  1282.     dst.mSpans.clear();
  1283.     while(src1 != src2) {
  1284.         uint32 p1 = src1[0];
  1285.         uint32 p2 = src1[1];
  1286.         src1 += 2;
  1287.  
  1288.         temp.mSpans.swap(dst.mSpans);
  1289.         VDPixmapConvolveRegion(dst, temp, r1, (p1 & 0xffff) - 0x8000, (p2 & 0xffff) - 0x8000, (p1 >> 16) - 0x8000);
  1290.     }
  1291. }
  1292.